package leetcode.graph.island;

/**
 * 200. 岛屿数量
 */
public class NumIslands {


    public static void main(String[] args) {
        NumIslands solution = new NumIslands();
        char[][] island = solution.createIsland();

        int count = solution.numIslands(island);
        System.out.println(count);

    }

    /**
     * 创建岛屿
     *
     * @return 二维数组
     */
    public char[][] createIsland() {
        return new char[][]{{'1', '1', '1'}, {'0', '1', '0'}, {'1', '1', '1'}};
    }


    /**
     * 自己做出来的
     * 感觉自己有点厉害 虽然时间复杂度较高
     *
     * 基本思路
     *      依次遍历这个二维数组, 遇到 1的时候, 往上下左右四个方向递归(相当于往四周寻找陆地), 直到遇到 0为止
     *      在递归遍历的过程中, 把遇到的节点设置为访问过, 最后遍历结束的时候岛屿数量加 1
     *      已经访问的陆地节点不需要重复访问, 也不能重复递归
     *      核心思想
     *          从当前陆地出发, 遍历周围所有的陆地, 算作一块岛屿, 访问的陆地需要设置为已访问, 不能重复递归遍历
     *
     * @param grid  岛屿
     * @return
     */
    public int numIslands0(char[][] grid) {
        // 岛屿数量
        int count = 0;
        int rowLen = grid.length;
        int colLen = grid[0].length;
        // 访问标识数组
        int[][] visited = new int[rowLen][colLen];

        for (int i = 0; i < rowLen; i++) {
            for (int j = 0; j < colLen; j++) {
                // 没访问过的节点才进行访问
                if(visited[i][j] == 0) {
                    // 当前节点是陆地, 进行递归, 访问相邻的所有陆地
                    if (grid[i][j] == '1') {
                        isLand(grid, visited, i, j);
                        // 岛屿数量加1
                        count++;
                    }
                }
            }
        }
        return count;
    }


    /**
     * 遍历访问当前陆地附近所有相邻的陆地(当前的节点是陆地)
     *
     *
     * @param grid      岛屿数组
     * @param visited   访问标识数组
     * @param i         陆地坐标
     * @param j         陆地坐标
     */
    public void isLand(char[][] grid, int[][] visited, int i, int j) {
        // 数组范围
        int rowLen = grid.length - 1;
        int colLen = grid[0].length - 1;

        // 设置当前陆地被访问过
        visited[i][j] = 1;

        // 往当前陆地的右边递归访问未访问过的陆地
        if (i <= rowLen && j + 1 <= colLen && visited[i][j + 1] == 0 && grid[i][j] == '1') {
            isLand(grid, visited, i, j + 1);
        }
        // 下
        if (i + 1 <= rowLen && j <= colLen && visited[i + 1][j] == 0 && grid[i][j] == '1' ) {
            isLand(grid, visited, i + 1, j);
        }
        // 上
        if (i - 1 <= rowLen && j <= colLen && i >= 1 && visited[i - 1][j] == 0 && grid[i][j] == '1') {
            isLand(grid, visited, i - 1, j);
        }
        // 左
        if (i <= rowLen && j - 1 <= colLen && j >= 1 && visited[i][j - 1] == 0 && grid[i][j] == '1') {
            isLand(grid, visited, i, j - 1);
        }
    }

    /**
     * 深度优先遍历 官方写法
     *
     * 相比我自己写的, 减少了一个额外的二维数组, 也就是访问标识数组
     *
     * @param grid  二维数组
     * @return
     */
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }

        int rowLen = grid.length;
        int colLen = grid[0].length;
        int count = 0;
        for (int r = 0; r < rowLen; ++r) {
            for (int c = 0; c < colLen; ++c) {
                if (grid[r][c] == '1') {
                    ++count;
                    dfs(grid, r, c);
                }
            }
        }

        return count;
    }

    void dfs(char[][] grid, int r, int c) {
        int rowLen = grid.length;
        int colLen = grid[0].length;

        if (r < 0 || c < 0 || r >= rowLen || c >= colLen || grid[r][c] == '0') {
            return;
        }

        // 已经访问过的陆地设置为0, 成为海洋, 防止重复遍历计算岛屿的数量
        grid[r][c] = '0';
        dfs(grid, r - 1, c);
        dfs(grid, r + 1, c);
        dfs(grid, r, c - 1);
        dfs(grid, r, c + 1);
    }
}
